Thread: Linked list task [C]

Please post the code you have done, so far, using [ CODE ] tags, so we can comment on it and guide you for the next steps. Please don't post a link to the code.

Please read the FAQ at the top of the page.

Code:

/**
 *  * structure Object
 *   */
typedef struct {
  int id;
  char *name;
} Object;

/**
 *  * Item of the list
 *   */
typedef struct item Item;
struct item {
  Object data;
  Item *next;
};

/**
 *  * type List
 *   */
typedef struct {
  Item *first;
} List;

/**
 *  * List initialization. Creates empty list. 
 *   */
List list_ctor()
{
  List list;
  list.first = NULL;
  return list;
}

/**
 *  * Itinialise item of list. From object creates item without successor.
 *   */
Item *item_ctor(Object data)
{
  Item *item;
  item = malloc(sizeof(Item));
  item->next = NULL;
  item->data = data;
  return item;
}

/**
 *  * Put item to the beggining of list.
 *   */
void list_insert_first(List * list, Item * i)
{
  i->next = list->first;
  list->first = i->next;
}

/**
 *  * Return true, if list is empty.
 *   */
bool list_empty(List * list)
{
  if (list->first == NULL)
    return true;
  else
    return false;
}

/**
 *  * Remove first element in list, if it is.
 *   */
void list_delete_first(List * list)
{
  Item *item = list->first;
  list->first = item->next;

}

/**
 *  * Returns number of elements in list.
 *   */
unsigned list_count(List * list)
{
  int count = 0;
  List *current = list;
  while (list != NULL) {
    count++;
    list->first = current->first;

  }
  return count;

}

/**
 *  * Finds item in list with with smallest identifier(id) Returns NULL, if
 *   * list is empty
 *    */
Item *list_find_minid(List * list)
{
  Item *item;

  if (list->first != NULL) {
    int min = item->data.id;
    while (list->first != NULL) {
      if (min > item->data.id) {
        min = item->data.id;
        return item;
      }
    }
  } else
    return NULL;

}

/**
 *  * Find item in list with corresponding name of object. Returns NULL, if
 *   * item like that doesn't exist
 *    */
Item *list_find_name(List * list, char *name)
{
  Item *item;
  while (list->first != NULL) {
    if (strcmp(name, item->data.name) == 0)
      return item;
    else
      return NULL;
  }
}

/**
 *  * Free list.
 *   */
void list_dtor(List * list)
{
  free(list);
}

/*-----------------------------------------------*/
int main()
{
  printf("list_ctor...\n");
  List list = list_ctor();

  printf("list_empty...\n");
  printf("Seznam prazdny: %s\n", list_empty(&list) ? "ano" : "ne");

  Item *item;

  Object o1 = { 42, "Honza" };
  printf("item_ctor...\n");
  item = item_ctor(o1);
  printf("list_insert_first...\n");
  list_insert_first(&list, item);

  printf("Seznam prazdny: %s\n", list_empty(&list) ? "ano" : "ne");
  printf("list_count...\n");
  printf("Pocet prvku v seznamu: %d\n", list_count(&list));

  Object o2 = { 2, "Malem" };
  item = item_ctor(o2);
  printf("list_insert_first...\n");
  list_insert_first(&list, item);

  Object o3 = { 0, "Kralem" };
  item = item_ctor(o3);
  printf("list_insert_first...\n");
  list_insert_first(&list, item);

  printf("Pocet prvku v seznamu: %d\n", list_count(&list));

  printf("Odstraneni prvniho prvku ze seznamu \n");
  list_delete_first(&list);
  printf("Pocet prvku v seznamu: %d\n", list_count(&list));

  // opetovne vlozeni objektu o1    
  item = item_ctor(o1);
  printf("list_insert_first...\n");
  list_insert_first(&list, item);

  printf("list_find_minid...\n");
  item = list_find_minid(&list);
  if (item != NULL) {
    printf("Polozka s nejmensim identifikatorem: {%d, " % s "}\n",
           item->data.id, item->data.name);
  } else
    printf("Polozka s nejmensim identifikatorem nenalezena\n");

  printf("list_find_name...\n");
  char *name = "Honza";
  item = list_find_name(&list, name);
  if (item != NULL) {
    printf("Polozka s daty %s nalezena\n", name);
  } else
    printf("Polozka s daty %s nenalezena.\n", name);

  printf("list_dtor...\n");
  list_dtor(&list);
  printf("Seznam prazdny: %s\n", list_empty(&list) ? "ano" : "ne");

  return 0;
}

Remember to do what rstanley said next time onwards.

Your minid function looks wrong. You must loop through your entire list to find the minimum which in your code just returns the first item->data.id. Same problem with your find name function. There's also code that is not required but I'll not make a mention of that yet.

Edit: Actually, minid function has an infinite loop looking closely (assuming list->first is not NULL). Also, you're doing checks with uninitialised pointers to objects that'll yield you garbage value comparison. I quickly glanced through your code (I've to go for dinner) and I think a lot of other things are wrong like the destructor but I'll have to look closely to see what you're actually trying to do.

Run the code in the debugger.

Code:

$ gcc -g foo.c
$ gdb -q ./a.out 
Reading symbols from ./a.out...done.
(gdb) run
Starting program: ./a.out 
list_ctor...
list_empty...
Seznam prazdny: ano
item_ctor...
list_insert_first...
Seznam prazdny: ano
list_count...
^C
Program received signal SIGINT, Interrupt.
0x00000000004007ab in list_count (list=0x7fffffffde00) at foo.c:92
92	    list->first = current->first;
(gdb) bt
#0  0x00000000004007ab in list_count (list=0x7fffffffde00) at foo.c:92
#1  0x0000000000400966 in main () at foo.c:162
(gdb) list
87	{
88	  int count = 0;
89	  List *current = list;
90	  while (list != NULL) {
91	    count++;
92	    list->first = current->first;
93	
94	  }
95	  return count;
96	
(gdb) print count
$1 = 683116588
(gdb)

Right, so go read the code for list_count and figure out how it got a count of 683116588 without even finishing the function.

> I already did all of these functions, yet I'm not sure if I did it right.
Lemme guess, you wrote all the code, fixed the compile errors and then tried to run it, only to find it didn't work.

That's the wrong approach.
Your write / compile / test loop needs to be much shorter - like just one function at a time.